package org.apache.commons.graph.view.finder

import com.gitee.wsl.collections.deque.ArrayDeque
import com.gitee.wsl.collections.internal.Preconditions.checkArgument
import com.gitee.wsl.ext.base.Arrays
import com.gitee.wsl.ext.base.SIZE
import com.gitee.wsl.ext.map.getOrDefault
import com.gitee.wsl.func.consumer.Consumer
import com.gitee.wsl.test.Preconditions.checkState
import org.apache.commons.graph.bean.Edge
import org.apache.commons.graph.view.IBackwardGraphView

/**
 * Implements a lowest common ancestor search algorithm.
 *
 *
 *
 * The LCA of a set of nodes is the node that is an ancestor to all of them but is not an ancestor of any other common
 * ancestor. In a non-tree, There may be multiple LCAs for a given set of search nodes.
 *
 *
 *
 * In a cyclic graph, the LCAs may not be well defined. Within a cycle, all elements are both above and below one
 * another, so there is no uniquely lowest element. If the set of common ancestors is rooted on a cycle, this
 * implementation returns one or more elements of that cycle. Those elements are chosen arbitrarily but
 * deterministically (as long as the underlying graph has deterministic iteration).
 */
//class LowestCommonAncestorFinder<N, E : Edge<N>>(private val graph: IBackwardGraphView<N, E>) {
//    /**
//     * An abstraction for `LowestCommonAncestorFinder::new`.
//     *
//     *
//     *
//     * This interface allows injection in tests.
//     */
//    fun interface Factory<N, E : Edge<N>> {
//        fun create(graph: IBackwardGraphView<N, E>): LowestCommonAncestorFinder<N, E>
//    }
//
//    /**
//     * A "color" for a node, encoded as a combination of other colors using a one-hot scheme.
//     */
//
//    private class Color(val bitset: Int) {
//        fun mix(other: Color): Color {
//            if (this.bitset == other.bitset) {
//                return this
//            }
//            return create(this.bitset or other.bitset)
//        }
//
//        fun contains(other: Color): Boolean {
//            return (this.bitset and other.bitset) == other.bitset
//        }
//
//
//        override fun equals(other: Any?): Boolean {
//            if (this === other) return true
//            if (other == null || this::class != other::class) return false
//
//            other as Color
//
//            if (bitset != other.bitset) return false
//
//            return true
//        }
//
//        override fun hashCode(): Int {
//            return this.bitset
//        }
//
//        companion object {
//            /**
//             * A set of commonly used colors to minimize allocations.
//             *
//             *
//             *
//             * An array is used to prevent bounds checking overhead.
//             */
//            private val COMMON_COLOR_CACHE: Array<Color> = Array<Color>(2 shl 5){ bitset: Int ->
//                Color(bitset)
//            }
//
//            /**
//             * A color that when mixed with any other color `x` returns `x`.
//             *
//             *
//             *
//             * Mixing this color is idempotent.
//             */
//            val BLANK: Color = checkNotNull(COMMON_COLOR_CACHE[0])
//
//            /**
//             * A color for common ancestors that indicates that there are lower common ancestors.
//             *
//             *
//             *
//             * Because this color sets its MSB high, it can never equal any other color. Also notice that mixing this
//             * [Color] with any other produces this [Color] again; mixing it is nullipotent.
//             */
//            val NOT_LOWEST: Color = Color(-1)
//
//            fun create(bitset: Int): Color {
//                if (bitset < 0) {
//                    checkArgument(bitset == -1)
//                    return NOT_LOWEST
//                } else if (bitset < COMMON_COLOR_CACHE.size) {
//                    return COMMON_COLOR_CACHE[bitset]
//                }
//                return Color(bitset)
//            }
//        }
//
//    }
//
//    private val searchColoring = LinkedHashMap<N, Color>()
//    private val searchQueue = ArrayDeque<N>()
//
//    /**
//     * Execute a search on all the elements of `roots`.
//     *
//     *
//     *
//     * This is a general-purpose, bare-bones implementation. There are lots of special case optimizations that could be
//     * applied.
//     */
//    fun findAll(roots: Set<N>): Set<N> {
//        // We reserved the MSB of each Color for bookkeeping.
//        checkArgument(roots.size <= Int.SIZE - 1, "Too many roots.")
//        checkState(this.searchColoring.isEmpty())
//
//        // In two's-complement, (2^n - 1) sets the lowest n bits high.
//        val allColor = Color.create((1 shl roots.size) - 1)
//
//        /**
//         * Paint up from each root using the color associated with that root.
//         *
//         *
//         *
//         * When done, the set of common ancestors is the set of nodes painted `allColor`.
//         */
//        var bitForRoot = 1
//        for (root in roots) {
//            val rootNode = root
//
//            val color = Color.create(bitForRoot)
//
//            this.searchColoring.merge(rootNode, color, { obj: Color, other: Color -> obj.mix(other) }) // Preserve any existing colors.
//            this.paintAncestors(rootNode, color)
//            bitForRoot = bitForRoot shl 1
//        }
//
//        /**
//         * For every common ancestor, paint all of its ancestors with a color indicating it is not the lowest.
//         */
//        this.searchColoring.forEach{ (node, color) ->
//            if (color == allColor) {
//                this.paintAncestors(node, Color.Companion.NOT_LOWEST)
//            }
//        }
//
//        val results = mutableSetOf<N>()
//        this.searchColoring.forEach{ (node, color) ->
//            if (color == allColor) {
//                results.add(node)
//            }
//        }
//
//        this.searchColoring.clear()
//        this.searchQueue.clear()
//        return results
//    }
//
//    /**
//     * Paint all nodes above `root` with `color`.
//     *
//     *
//     *
//     * `root` itself will not have its color changed. `color` will be mixed with all existing colors on
//     * ancestor nodes.
//     */
//    private fun paintAncestors(root: N, color: Color) {
//        checkState(this.searchQueue.isEmpty())
//
//        this.searchQueue.addLast(root)
//
//        while (!this.searchQueue.isEmpty()) {
//            val curr = this.searchQueue.removeFirst()
//            graph.forEachSource(curr, Consumer { parent: N ->
//                if (parent != root) {
//                    val oldColor: Color = this.searchColoring.getOrDefault(parent, Color.Companion.BLANK)
//                    if (!oldColor.contains(color)) {
//                        // Only explore in directions that have not yet been painted.
//                        this.searchQueue.addLast(parent)
//                        this.searchColoring[parent] = oldColor.mix(color)
//                    }
//                }
//            })
//        }
//    }
//}
